\section{Challenges}



According to the public cloud architecture~\ref{sec:back},
once the basic network is set up, configuring various aspects of the
network, e.g., firewall rules, routing adjacencies, etc., requires
coordinated changes across multiple elements in the tenant's
topology. A number of things could go wrong in configuring such a
complex system, including incorrect virtual machine settings, or
misconfigured gateways or middleboxes. To complicate matters further,
failures can occur in the underlying physical infrastructure elements
which are not visible in the virtual networks.  Hence, diagnosing
virtual networks in a large scale cloud environment introduces several
concomitant technical challenges described further below.

{\bf Challenge 1: Preserving abstractions.} Tenants work with an
abstract view of the network, and the diagnosis approach should
continue to preserve this abstract view.  Details of the physical
locations from which data is being gathered should be hidden, allowing
tenants to apply analyze data that corresponds to their logical view
of the network.

{\bf Challenge 2: Low overhead network information collection.}  Most
network diagnostic mechanisms collect information by tracing flows on
network devices~\cite{ndb, ofrewind}.  In traditional enterprise and
ISP networks, operators and users rely on the built-in mechanisms on
physical switches and routers for network diagnosis such as NetFlow,
sFlow or port mirroring. In the cloud environment, however, the
virtual network is constructed on software components, such as virtual
switches and virtual routers.  Trace capture for high throughput flows
imposes significant traffic volume into the network and switches.  As
the cloud infrastructure is shared among tenants, the virtual network
diagnostic mechanisms must limit their impact on switching performance
and the effect on other tenant or application flows.

{\bf Challenge 3: Scaling to many tenants.}  Providing a network
diagnosis service to a single tenant requires collection of flows of
interest and data analysis on the (potentially distributed) flow
data. All these operations require either network bandwidth or CPU
cycles. In a large-scale cloud with a large number of tenants who may
request diagnosis services simultaneously, data collection and
analysis can impose significant
bottlenecks impacting both the speed and effectiveness of
troubleshooting and also affecting prevalent network
traffic.

{\bf Challenge 4: Disambiguating and correlating flows.} To provide
network diagnosis services for cloud tenants, the service provider
must be able to identify the right flows for different tenants and
correlate them among different network components. This problem is
particularly challenging in cloud virtual overlay networks for two
reasons: (1) Tunneling/encapsulation makes tracing
tenant-specific traffic on intermediate hops of a tunnel
difficult; (2) middleboxes and other services may transform
packets, further complicating correlation.
For example, NATs rewrite the IP addresses/ports; a WAN optimizer can
``compress'' the payload from multiple incoming packets into a few
outgoing packets, etc.

